package middle;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import util.PrintUtils;

public class Solution_137 {

    public int singleNumber(int[] nums) {
        long rst = 0;
        int base = 1;
        while (true) {
            boolean flag = false;
            int count = 0;
            for (int i = 0; i < nums.length; i++) {
                count += nums[i] % 2;
                nums[i] = nums[i] >>> 1;
                if (nums[i] != 0) {
                    flag = true;
                }
            }
            rst += (count % 3L * base);
            base <<= 1;
            if (!flag) {
                break;
            }
        }
        return (int)rst;
    }

    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        List<int[]> list = new ArrayList<>();
        int begin = intervals[0][0], end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= end) {
                //                end = intervals[i][1];
                end = Math.max(end, intervals[i][1]);
            } else {
                list.add(new int[]{begin, end});
                begin = intervals[i][0];
                end = intervals[i][1];
            }
        }
        list.add(new int[]{begin, end});
        return list.toArray(new int[][]{});
    }

    public void rotate(int[][] matrix) {
        int round = (matrix.length + 1) / 2;
        for (int i = 0; i < matrix.length / 2; i++) {
            for (int j = 0; j < round; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[matrix.length - 1 - j][i];
                matrix[matrix.length - 1 - j][i] = matrix[matrix.length - 1 - i][matrix.length - 1 - j];
                matrix[matrix.length - 1 - i][matrix.length - 1 - j] = matrix[j][matrix.length - 1 - i];
                matrix[j][matrix.length - 1 - i] = temp;
            }
        }
    }

    public void setZeroes(int[][] matrix) {
        Set<Integer> rows = new HashSet<>();
        Set<Integer> cols = new HashSet<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    rows.add(i);
                    cols.add(j);
                }
            }
        }
        for (Integer row : rows) {
            for (int j = 0; j < matrix[0].length; j++) {
                matrix[row][j] = 0;
            }
        }
        for (Integer col : cols) {
            for (int i = 0; i < matrix.length; i++) {
                matrix[i][col] = 0;
            }
        }
    }

    public int[] findDiagonalOrder(int[][] mat) {
        int row = mat.length, col = mat[0].length;
        int[] array = new int[row * col];
        int i = 0, j = 0, count = 0;
        boolean flag = true;
        while (count < array.length) {
            array[count++] = mat[i][j];
            if ((flag && (i == 0 || j == col - 1)) || (!flag && (j == 0 || i == row - 1))) {
                if (flag) {
                    if (j == col - 1) {
                        i++;
                    } else {
                        j++;
                    }
                } else {
                    if (i == row - 1) {
                        j++;
                    } else {
                        i++;
                    }
                }
                flag = !flag;
            } else {
                if (flag) {
                    i--;
                    j++;
                } else {
                    i++;
                    j--;
                }
            }
        }
        return array;
    }

    public String longestCommonPrefix(String[] strs) {
        int count = 0;
        while (true) {
            char pre = ' ';
            boolean flag = false;
            for (int i = 0; i < strs.length; i++) {
                if (count >= strs[i].length()) {
                    flag = true;
                    break;
                }
                char c = strs[i].charAt(count);
                if (i == 0) {
                    pre = c;
                } else {
                    if (pre != c) {
                        flag = true;
                        break;
                    }
                }
            }
            if (!flag) {
                count++;
            } else {
                break;
            }
        }
        return strs[0].substring(0, count);
    }

    public String longestPalindrome(String s) {
        boolean[][] flags = new boolean[s.length()][s.length()];
        for (int i = 0; i < flags.length; i++) {
            for (int j = 0; j < flags[i].length - i; j++) {
                if (s.charAt(j + i) == s.charAt(j)) {
                    flags[j][i + j] = i < 2 || flags[j + 1][i + j - 1];
                } else {
                    flags[j][i + j] = false;
                }
            }
        }
        for (int length = s.length(); length > 0; length--) {
            for (int i = 0, j = i + length - 1; j < s.length(); i++, j++) {
                if (flags[i][j]) {
                    return s.substring(i, j + 1);
                }
            }
        }
        return "";
    }

    public String reverseWords1(String s) {
        String[] strings = s.split(" ");
        StringBuilder builder = new StringBuilder();
        for (int i = strings.length - 1; i >= 0; i--) {
            if (!strings[i].equals("")) {
                builder.append(strings[i]).append(' ');
            }
        }
        return builder.substring(0, builder.length() - 1);
    }

    public int strStr(String haystack, String needle) {
        int[] next = new int[needle.length()];
        next[0] = -1;
        for (int i = 1; i < needle.length(); i++) {
            for (int j = 0; j < i - 1; j++) {
                String temp = needle.substring(0, i);
                String tt = needle.substring(0, j + 1);
                if (temp.startsWith(tt) && temp.endsWith(tt)) {
                    next[i] = tt.length();
                }
            }
        }
        PrintUtils.arrayInt(next);

        int i = 0, j = 0;
        while (i < haystack.length() && j<needle.length()) {
            if (haystack.charAt(i) != needle.charAt(j)) {
                int nextJ = next[j];
                if (nextJ < 0) {
                    i++;
                    j = 0;
                } else {
                    j = nextJ;
                }
            } else {
                i++;
                j++;
            }
        }
        return j == needle.length() ? i - needle.length() : -1;
    }

    public void reverseString(char[] s) {
        int i = 0, j = s.length - 1;
        while (i < j) {
            char c = s[i];
            s[i] = s[j];
            s[j] = c;
            i++;
            j--;
        }
    }

    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; i+=2) {
            sum += nums[i];
        }
        return sum;
    }

    public int[] twoSum(int[] numbers, int target) {
        int i = 0, j = numbers.length - 1;
        while (true) {
            int num = numbers[i] + numbers[j];
            if (num == target) {
                break;
            } else if (num < target) {
                i++;
            } else {
                j--;
            }
        }
        return new int[]{i+1, j+1};
    }

    public int removeElement(int[] nums, int val) {
        int slow = 0, fast = 0;
        for (; fast < nums.length; fast++) {
            if (nums[fast]!=val) {
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }

    public int findMaxConsecutiveOnes(int[] nums) {
        int begin = -1, end = -1, max = 0;
        for (int i = 0; i <= nums.length; i++) {
            if (i == nums.length) {
                if (begin >= 0) {
                    max = Math.max(max, end - begin + 1);
                    begin = -1;
                    end = -1;
                }
            } else if (nums[i] == 1) {
                if (begin < 0) {
                    begin = i;
                }
                end = i;
            } else if (begin >= 0) {
                max = Math.max(max, end - begin + 1);
                begin = -1;
                end = -1;
            }
        }
        return max;
    }

    public int minSubArrayLen(int target, int[] nums) {
        int minCount = Integer.MAX_VALUE, sum = nums[0], i = 0, j = 1;
        while (i < nums.length || j<nums.length) {
            if (sum < target) {
                if (j == nums.length) {
                    break;
                }
                sum += nums[j++];
            } else {
                minCount = Math.min(j - i, minCount);
                sum -= nums[i++];
            }
        }
        return minCount == Integer.MAX_VALUE ? 0 : minCount;
    }

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> rst = new ArrayList<>(numRows);
        for (int i = 0; i < numRows; i++) {
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i || i == 0) {
                    list.add(1);
                } else {
                    list.add(rst.get(i - 1).get(j-1) + rst.get(i - 1).get(j));
                }
            }
            rst.add(list);
        }
        return rst;
    }

    public List<Integer> getRow(int rowIndex) {
        List<Integer> list = new ArrayList<>(rowIndex + 1);
        for (int i = 0; i < rowIndex + 1; i++) {
            int left = 0, right;
            for (int j = 0; j <= i; j++) {
                if (j == 0) {
                    right = 1;
                } else if (j < i) {
                    right = list.get(j);
                } else {
                    right = 0;
                }
                int temp = right;
                if (j == i) {
                    list.add(left + right);
                } else {
                    list.set(j, left + right);
                    left = temp;
                }
            }
        }
        return list;
    }

    public String reverseWords(String s) {
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; ) {
            int j = i + 1;
            while (j < chars.length) {
                if (chars[j] == ' ') {
                    break;
                }
                j++;
            }
            reverse(chars, i, j - 1);
            i = j + 1;
            while (i < chars.length) {
                if (chars[i] != ' ') {
                    break;
                }
                i++;
            }
        }
        return new String(chars);
    }

    private void reverse(char[] chars, int i, int j) {
        while (i < j) {
            char c = chars[i];
            chars[i] = chars[j];
            chars[j] = c;
            i++;
            j--;
        }
    }

    public int findMin(int[] nums) {
        int i = 0, j = nums.length - 1;
        while (i + 1 < j) {
            int middle = (i + j + 1) / 2;
            if (nums[i] <= nums[middle] && nums[middle] <= nums[j]) {
                return nums[i];
            } else {
                if (nums[middle] < nums[i]) {
                    j = middle;
                } else {
                    i = middle + 1;
                }
            }
        }
        return Math.min(nums[i], nums[j]);
    }

    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int slow = 1, fast = 1;
        while (fast < nums.length) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow++] = nums[fast];
            }
            fast++;
        }
        return slow;
    }

    public void moveZeroes(int[] nums) {
        int slow = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[slow] = nums[i];
                if (i > slow) {
                    nums[i] = 0;
                }
                slow++;
            }
        }
    }

    public static void main(String[] args) {
        Solution_137 model = new Solution_137();
//        System.out.println(model.singleNumber(new int[]{-2,-2,1,1,4,1,4,4,-4,-2}));
//        System.out.println(model.singleNumber(new int[]{2,2,3,2}));
//        System.out.println(model.singleNumber(new int[]{0,1,0,1,0,1,99}));
        for (int i = 0; i < 33; i++) {
            System.out.println("i : " + i + " = " + (-1 >>> i));
        }
    }
}
